/**
 * 面试题 04.10. 检查子树
 * https://leetcode-cn.com/problems/check-subtree-lcci/
 */
public class Solutions_mianshi_04_10 {
    public static void main(String[] args) {
//        String treeStr1 = "[1 2 3]";
//        String treeStr2 = "[2]";  // output: true

        String treeStr1 = "[1 # 2 4]";
        String treeStr2 = "[3 2]";  // output: false

        TreeNode t1 = MyTreeNodeUtils.deserialize(treeStr1);
        TreeNode t2 = MyTreeNodeUtils.deserialize(treeStr2);

        boolean result = checkSubTree(t1, t2);
        System.out.println(result);
    }

    public static boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            // 结束条件：都为 null 时，说明两个子树结构相同
            return t2 == null;
        }
        if (t1.val == t2.val) {
            // 根节点相同，递归查找左右子树是否全部相同
            return checkSubTree(t1.left, t2.left) && checkSubTree(t1.right, t2.right);
        }
        // 根节点不同时，递归查找 t1 的左、右子树
        // t1 的左、右子树中，有一侧匹配到 t2 则返回 true
        return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }
}
